The present invention relates to an improvement in a pattern matching system for comparing two patterns expressed as a sequence of feature vectors to compute a measure (which will be called a "dissimilarity") for discrimination between the two patterns.
As speech recognizing means, a variety of methods have been tried. Of these, there has been proposed a relatively simple and effective method of pattern matching by normalizing a nonlinear extension, as is disclosed in U.S. Pat. No. 3,816,722. A speech pattern has non-linear and complex fluctuations due to fluctuations in speaking speed. This makes it necessary to consider the time-axis fluctuation when input and reference patterns are to be matched. This method warps the time axis of one of the patterns to determine the corresponding relationship (which will be called a "time-normalized function") of the time axis for approximating it to the other pattern thereby to determine a discrimination having a normalized time-axis fluctuation. The principle based on that method will be schematically described in the following (which will be called a "horizontal algorithm").
An input pattern A and an n-th reference pattern B.sup.n are expressed as a sequence of feature vectors (one of which will be called "one frame") by the following Equations: EQU A=a.sub.1, a.sub.2, - - - , a.sub.i, - - - a.sub.I ( 1);
and EQU B.sup.n =b.sub.1, b.sub.2, - - - , b.sub.j.sup.n, - - - , b.sub.J.sup.n ( 2)
When a function (i.e., the time-normalized function) for realizing a mapping from the time axis i of the input pattern onto the corresponding j of the reference pattern is expressed by j=j(i), the normalized difference D (A, B.sup.n) in which the time-axis fluctuation is normalized is attained as a solution of the following minimization problem: ##EQU1## where EQU d(i,j)=.vertline..vertline.a.sub.1 -b.sub.j.sup.n .vertline..vertline.(4)
This minimization problem is to derive g.sub.n (I, J) by computing (for one horizontal line) the following asymptotic equation from i=j-r to i=j+r for fixed j: ##EQU2## under the following initial condition: EQU g.sub.n =(0, 0)=0 (5)
and by advancing the computation of one horizontal line from j=1 to j=J along the j-axis. The value g.sub.n (I, J) thus derived is the normalized dissimilarity D(A, B.sup.n).
The computation of the j-th line of the horizontal algorithm requires the (i-r)th to (i+r)th frames of the input pattern and the j-th frame of the reference pattern. The computation of the (j+1)th line requires the (i-r+1)th to (i+r+1)th frames of the input pattern and the (j+1)th frame of the reference pattern. If the (i-r)th frame of the input pattern is neglected for the frame which was used for computation of the j-th line and if the (i+r+1)th frame of the input pattern and the (j+1)th frame of the reference pattern are added, however, it is possible to execute the computation of the (j+1)th line. In other words, the pattern matching system for executing the horizontal algorithm is equipped with pattern buffers for the (2r+1) frames of the input pattern and for one frame of the reference pattern and reads in one frame of the input pattern and one frame of the reference pattern for the one horizontal line computation thereby to compute the distance of Equation (4) and the asymptotic Equation (6).
If one horizontal line computation is repeated for each reference pattern when the normalized dissimilarity from N reference patterns is to be determined, the value g.sub.n (i, j) derived for the j-th line is used for each reference pattern, when the (j+1)th line is to be computed, thereby necessitating the temporary storage of the values g.sub.n (i, j) of N reference patterns. Keeping out the temporary storage, the computations of one horizontal line are conducted from 1 to J for each reference pattern. In this case, the dissimilarities g.sub.n (i, j) can be consecutively stored in the memories for three lines, i.e., j-th, (j-1)th and (j-2)th lines so that the number of the memories for the dissimilarities g.sub.n (i, j) can be reduced. Since the operations of deriving the normalized dissimilarities from one reference pattern are repeated N times, however, the computations are started after the final frame of the input pattern is attained.
As has been described above, there is not much transfer of pattern data in the pattern matching system for executing the horizontal algorithm. However, the pattern matching system has shortcomings in that it requires buffer memories having a large capacity for the (2r+2) frames of the feature vectors, and in that its response is delayed because the computations cannot be started before the final frame of the input pattern is attained.
On the other hand, there has been proposed by the present inventor and others, as is disclosed in U.S. patent application Ser. No. 447,829, a method (which will be called a "vertical algorithm") in which the order of computing the asymptotic Equation (6) is interchanged between i and j.
According to this method, the value g.sub.n (I, J), i.e., the normalized dissimilarity D(A, B.sup.n) is derived by computing (for one column) the asymptotic Equation (6) from j=i-r to J=i+r for fixed i and by advancing the computations of the one column from i=1 to i=I along the i-axis. The computation of one column of the vertical algorithm can be advanced in synchronism with the input of each frame of the input pattern, because it is conducted along the time axis i of the input pattern, so that its response time can be shortened.
When the dissimilarities from the N reference patterns are to be computed in synchronism with the input of the input pattern, however, the one column computation is repeated for the N reference patterns, and the resultant dissimilarity g.sub.n (i, j) is temporarily stored for each reference pattern so that it is used for the next column computation. This makes it necessary to provide memories of one column of the dissimilarity g.sub.n (i, j), respectively, for the N reference patterns. For one column computation, on the other hand, the refernce pattern buffers need be provided for only one frame because the reference patterns are consecutively interchanged.
As has been described hereinbefore, the pattern matching system for executing the vertical algorithm can advance the computations in synchronism with the input of each frame of the input pattern so that the computed result can be obtained immediately after the input of the final frame of the input pattern. Moreover, the pattern buffer memories required for the distance computation may have a small capacity for one frame of the input pattern and one frame of the reference pattern. Since N reference patterns must be transferred for each frame of the input pattern, however, there arises a defect that the required transfer time of the reference patterns is I times as high as that of the horizontal algorithm. In order to cure this defect, therefore, it is necessary to drop the access time of the memories to 1/I; otherwise the circuitry is complex and expensive.